1. Field
Embodiments of the invention relate to the field of memory, and more specifically to performing inserts and lookups in memory.
2. Background Information and Description of Related Art
To enable faster lookups in a memory, several algorithms group a number of entries into a section. An original search key is then compared with each entry in the section in a single lookup. If the comparisons to each entry are performed sequentially, the lookup is slow, since it takes a number of cycles to traverse all the entries. If the comparisons to each entry are performed in parallel, the logic needed to implement the parallel comparison of each entry with the search key takes more chip area and is relatively costly.
An alternative method is to sort the entries in a section and store discriminant bits that differentiate the sorted entries. This method allows for fast lookups but puts a penalty on inserts, since inserts may require the entries to be resorted. For example, for each insert into a section with N number of entries, if the entries are resorted, there will be N memory reads and N memory writes required.